/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x) {
    if (head == NULL)
    {
        return head;
    }
    ListNode* pcur, * prve, * next, * newHead, * newTail;
    pcur = head;
    prve = NULL;
    newHead = newTail = (ListNode*)malloc(sizeof(ListNode));
    while (pcur)
    {
        next = pcur->next;
        if (pcur->val < x)
        {
            prve = pcur;
        }
        else
        {
            if (prve == NULL)
                head = next;
            else
                prve->next = next;
            newTail->next = pcur;
            newTail = newTail->next;
        }
        pcur = next;
    }

    newTail->next = NULL;
    ListNode* mid = newHead->next;
    free(newHead);
    newHead = NULL;
    if (prve == NULL)
    {
        return mid;
    }
    prve->next = mid;
    return head;

}